package algorithm

import "fmt"

type Node struct {
	Key string
	Val string
	Pre *Node
	Nex *Node
 }

func (n *Node) Init(key, val string) {
	n.Key = key
	n.Val = val
}

var head, end *Node
var limit int

type LruCache struct {
	Limit   int
	HashMap map[string]*Node
}

func GetLruCache(limit int) *LruCache {
	lruCache := LruCache{Limit: limit}
	lruCache.HashMap = make(map[string]*Node, limit)
	return &lruCache
}

func (l *LruCache) Get(key string) string {
	if v, ok := l.HashMap[key]; ok {
		l.refreshNode(v)
		return v.Val
	} else {
		return ""
	}
}
func (l *LruCache) Put(key, val string) {
	if v, ok := l.HashMap[key]; ok {
		v.Val = val
		l.refreshNode(v)
	} else {
		if len(l.HashMap) >= l.Limit {
			oldKey := l.removeNode(head)
			delete(l.HashMap, oldKey)
		}
		node := Node{Key: key, Val: val}
		l.addNode(&node)
		l.HashMap[key] = &node
	}
}

func (l *LruCache) refreshNode(node *Node) {
	if node == end {
		return
	}
	l.removeNode(node)
	l.addNode(node)
}
func (l *LruCache) removeNode(node *Node) string {
	if node == end {
		end = end.Pre
	} else if node == head {
		head = head.Nex
	} else {
		node.Pre.Nex = node.Nex
		node.Nex.Pre = node.Pre
	}
	return node.Key
}
func (l *LruCache) addNode(node *Node) {
	if end != nil {
		end.Nex = node
		node.Pre = end
		node.Nex = nil
	}
	end = node
	if head == nil {
		head = node
	}
}
func RunCaseLru() {
	lru := GetLruCache(4)
	lru.Put("case1", "case1")
	lru.Put("case2", "case2")
	lru.Put("case3", "case3")
	lru.Put("case4", "case4")
	lru.Get("case2")
	lru.Put("case3", "yonghuxinxibiangeng")
	lru.Put("case6", "iangeng")
	fmt.Println(lru.Get("case1"))
	fmt.Println(lru.Get("case2"))
	fmt.Println(lru.Get("case3"))
	fmt.Println(lru.Get("case4"))
	fmt.Println(lru.HashMap)
}
